import java.util.Comparator;

public class Test {
    //Top-K问题
    //共有N个元素，取前K个最小元素
    //方法1
    public int[] smallestK(int[] arr,int k){
        java.util.PriorityQueue<Integer> priorityQueue=new java.util.PriorityQueue<>();
        for (int i = 0; i <arr.length ; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] ret=new int[k];
        for (int i = 0; i <k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;
    }
    //方法2
    public int[] smallest2(int[] arr,int k){
        class IntCom implements Comparator<Integer> {
            @Override
            public int compare(Integer o1, Integer o2) {
                //return o1.compareTo(o2);//小根堆
                return o2.compareTo(o1);//大根堆
            }
        }
        //底层创建的是小根堆
        java.util.PriorityQueue<Integer> priorityQueue=new java.util.PriorityQueue<>(new IntCom());
        for (int i = 0; i <k; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] ret=new int[k];
        for (int i = k; i <arr.length; i++) {
            int peekVal=priorityQueue.peek();
            if (peekVal>arr[k]){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i <k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array={5,7,2,1,4,3,8,6};
        Test queue=new Test();
        // int[] ret=queue.smallestK(array,4);
        int[] ret= queue.smallest2(array,4);
        for (int i = 0; i <ret.length; i++) {
            System.out.print(ret[i]+" ");
        }
    }

}
